{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Addition to Make Integer Beautiful"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: makeIntegerBeautiful"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #美丽整数的最小增量"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个正整数 <code>n</code> 和 <code>target</code> 。</p>\n",
    "\n",
    "<p>如果某个整数每一位上的数字相加小于或等于 <code>target</code> ，则认为这个整数是一个 <strong>美丽整数</strong> 。</p>\n",
    "\n",
    "<p>找出并返回满足 <code>n + x</code> 是 <strong>美丽整数</strong> 的最小非负整数 <code>x</code> 。生成的输入保证总可以使 <code>n</code> 变成一个美丽整数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 16, target = 6\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>最初，n 是 16 ，且其每一位数字的和是 1 + 6 = 7 。在加 4 之后，n 变为 20 且每一位数字的和变成 2 + 0 = 2 。可以证明无法加上一个小于 4 的非负整数使 n 变成一个美丽整数。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 467, target = 6\n",
    "<strong>输出：</strong>33\n",
    "<strong>解释：</strong>最初，n 是 467 ，且其每一位数字的和是 4 + 6 + 7 = 17 。在加 33 之后，n 变为 500 且每一位数字的和变成 5 + 0 + 0 = 5 。可以证明无法加上一个小于 33 的非负整数使 n 变成一个美丽整数。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 1, target = 1\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>最初，n 是 1 ，且其每一位数字的和是 1 ，已经小于等于 target 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>12</sup></code></li>\n",
    "\t<li><code>1 &lt;= target &lt;= 150</code></li>\n",
    "\t<li>生成的输入保证总可以使 <code>n</code> 变成一个美丽整数。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-addition-to-make-integer-beautiful](https://leetcode.cn/problems/minimum-addition-to-make-integer-beautiful/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-addition-to-make-integer-beautiful](https://leetcode.cn/problems/minimum-addition-to-make-integer-beautiful/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['16\\n6', '467\\n6', '1\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeIntegerBeautiful(self, n: int, target: int) -> int:\n",
    "        n = str(n)\n",
    "        len_n = len(n)\n",
    "        arr = [int(n[i]) for i in range(len_n)]\n",
    "        sum_n = sum(arr)\n",
    "        res = 0\n",
    "        idx = 1\n",
    "        while sum_n > target:\n",
    "            temp1 = arr[-idx]\n",
    "            res += (10-temp1) * (10 ** (idx-1))\n",
    "            if idx < len_n:\n",
    "                idx += 1\n",
    "            arr[-idx] += 1\n",
    "            sum_n = sum_n - temp1 + 1\n",
    "        return res\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeIntegerBeautiful(self, n: int, target: int) -> int:\n",
    "        # 凑数\n",
    "        if sum(int(i) for i in str(n)) <= target:\n",
    "            return 0\n",
    "        sn = str(n)\n",
    "        l = len(sn)\n",
    "        for i, v in enumerate(sn):\n",
    "            target -= int(v)\n",
    "            if target <= 0:\n",
    "                return 10**(l-i) - int(sn[i:])\n",
    "        return 0\n",
    "\n",
    "        # TLE - 暴力 除法\n",
    "        x = 0\n",
    "        while 1:\n",
    "            num = n + x\n",
    "            s = 0\n",
    "            while num:\n",
    "                s += num % 10\n",
    "                num = num // 10\n",
    "            if s <= target:\n",
    "                 return x\n",
    "            x += 1\n",
    "\n",
    "        # TLE - 暴力 转换\n",
    "        x = 0\n",
    "        while 1:\n",
    "            if sum(int(i) for i in str(n + x)) <= target:\n",
    "                return x\n",
    "            x += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeIntegerBeautiful(self, n: int, target: int):\n",
    "        nums=list(map(int,list(str(n))))\n",
    "        n,s=len(nums),sum(nums)\n",
    "        i=n-1\n",
    "        ans=0\n",
    "        while s>target:\n",
    "            if i==n-1:\n",
    "                s+=1\n",
    "                ans+=10**(n-1-i)*(10-nums[i])\n",
    "            else:\n",
    "                ans+=10**(n-1-i)*(10-nums[i]-1)\n",
    "            s-=nums[i]\n",
    "            i-=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeIntegerBeautiful(self, n: int, target: int) -> int:\n",
    "        tail = 1\n",
    "        while True:\n",
    "            m = x = n + (tail - n % tail) % tail  # 进位后的数字\n",
    "            s = 0\n",
    "            while x:\n",
    "                s += x % 10\n",
    "                x //= 10\n",
    "            if s <= target: return m - n\n",
    "            tail *= 10\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeIntegerBeautiful(self, n: int, target: int) -> int:\n",
    "        # 凑数\n",
    "        if sum(int(i) for i in str(n)) <= target:\n",
    "            return 0\n",
    "        sn = str(n)\n",
    "        l = len(sn)\n",
    "        for i, v in enumerate(sn):\n",
    "            target -= int(v)\n",
    "            if target <= 0:\n",
    "                return 10**(l-i) - int(sn[i:])\n",
    "        return 0\n",
    "\n",
    "\n",
    "        # TLE - 暴力 除法\n",
    "        x = 0\n",
    "        while 1:\n",
    "            num = n + x\n",
    "            s = 0\n",
    "            while num:\n",
    "                s += num % 10\n",
    "                num = num // 10\n",
    "            if s <= target:\n",
    "                 return x\n",
    "            x += 1\n",
    "\n",
    "        # TLE - 暴力 转换\n",
    "        x = 0\n",
    "        while 1:\n",
    "            if sum(int(i) for i in str(n + x)) <= target:\n",
    "                return x\n",
    "            x += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeIntegerBeautiful(self, n: int, target: int) -> int:\n",
    "        res = 0\n",
    "        ls = [int(c) for c in str(n)]\n",
    "        Sum = sum(ls)\n",
    "        if Sum<=target:\n",
    "            return 0\n",
    "        flag = 1\n",
    "        ls[-1] -= 1\n",
    "        for i in ls[::-1]:\n",
    "            res += (9-i)*flag\n",
    "            flag *= 10\n",
    "            Sum -= i\n",
    "            if Sum<=target:\n",
    "                return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeIntegerBeautiful(self, n: int, target: int) -> int:\n",
    "        def f(x: int) -> int:\n",
    "            y = 0\n",
    "            while x:\n",
    "                y += x % 10\n",
    "                x //= 10\n",
    "            return y\n",
    "\n",
    "        x = 0\n",
    "        while f(n + x) > target:\n",
    "            y = n + x\n",
    "            p = 10\n",
    "            while y % 10 == 0:\n",
    "                y //= 10\n",
    "                p *= 10\n",
    "            x = (y // 10 + 1) * p - n\n",
    "        return x\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def makeIntegerBeautiful(self, n: int, target: int) -> int:\n",
    "        ans = 0\n",
    "        x = 1\n",
    "        while True:\n",
    "            lst = [int(w) for w in str(n)]\n",
    "            while lst and lst[-1] == 0:\n",
    "                x *= 10\n",
    "                lst.pop()\n",
    "            if sum(lst) <= target:\n",
    "                break\n",
    "            last = 10 - lst[-1]\n",
    "            ans += x*last\n",
    "            n = int(\"\".join([str(w) for w in lst])) + last\n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeIntegerBeautiful(self, n: int, target: int) -> int:\n",
    "        s=[]\n",
    "        t=n\n",
    "        while t>0:\n",
    "            s.append(t%10)\n",
    "            t//=10\n",
    "        total=sum(s)\n",
    "        if total<=target:\n",
    "            return 0\n",
    "        ret=[]\n",
    "        acc=0\n",
    "        for i,num in enumerate(s):\n",
    "            if not num and not acc:\n",
    "                ret.append('0')\n",
    "                continue\n",
    "            if not i:\n",
    "                total+=1\n",
    "            ret.append(str(10-num-acc))\n",
    "            acc=1\n",
    "            total-=num\n",
    "            #print(ret,total,acc,num)\n",
    "            if total<=target:\n",
    "                return int(''.join(ret[::-1]))\n",
    "        if ret:\n",
    "            return int(''.join(ret[::-1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeIntegerBeautiful(self, n: int, target: int) -> int:\n",
    "        tail = 1\n",
    "        while True:\n",
    "            m = x = n + (tail - n % tail) % tail  # 进位后的数字\n",
    "            s = 0\n",
    "            while x:\n",
    "                s += x % 10\n",
    "                x //= 10\n",
    "            if s <= target: return m - n\n",
    "            tail *= 10\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeIntegerBeautiful(self, n: int, target: int) -> int:\n",
    "        # 凑数\n",
    "        if sum(int(i) for i in str(n)) <= target:\n",
    "            return 0\n",
    "        sn = str(n)\n",
    "        l = len(sn)\n",
    "        for i, v in enumerate(sn):\n",
    "            target -= int(v)\n",
    "            if target <= 0:\n",
    "                return 10**(l-i) - int(sn[i:])\n",
    "        return 0\n",
    "\n",
    "        # TLE - 暴力 除法\n",
    "        x = 0\n",
    "        while 1:\n",
    "            num = n + x\n",
    "            s = 0\n",
    "            while num:\n",
    "                s += num % 10\n",
    "                num = num // 10\n",
    "            if s <= target:\n",
    "                 return x\n",
    "            x += 1\n",
    "\n",
    "        # TLE - 暴力 转换\n",
    "        x = 0\n",
    "        while 1:\n",
    "            if sum(int(i) for i in str(n + x)) <= target:\n",
    "                return x\n",
    "            x += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeIntegerBeautiful(self, n: int, target: int) -> int:\n",
    "        nums = []\n",
    "        tsum = 0\n",
    "        while(n > 0):\n",
    "            nums.append(n % 10)\n",
    "            tsum += n % 10\n",
    "            n = n // 10\n",
    "        if(tsum <= target):\n",
    "            return 0 \n",
    "        nums.append(0)\n",
    "        result = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if(nums[i] == 0):\n",
    "                continue\n",
    "            result += (10-nums[i])*10**i\n",
    "            tsum -= nums[i]\n",
    "            nums[i] = 0\n",
    "            carry = 1\n",
    "            for j in range(i+1,n):\n",
    "                if(nums[j] + carry < 10):\n",
    "                    tsum += carry\n",
    "                    nums[j] += carry\n",
    "                    break\n",
    "                else:\n",
    "                    tsum -= nums[j]\n",
    "                    nums[j] = 0\n",
    "                    carry = 1\n",
    "            if(tsum <= target):\n",
    "                return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def makeIntegerBeautiful(self, n: int, target: int) -> int:\r\n",
    "        s = str(n)\r\n",
    "        sm = sum(int(c) for c in s)\r\n",
    "        if sm <= target:\r\n",
    "            return 0\r\n",
    "        res = 0\r\n",
    "        d = 1\r\n",
    "        for i in range(len(s))[::-1]:\r\n",
    "            total = 10 if i == len(s) - 1 else 9\r\n",
    "            res = d * (total - int(s[i])) + res\r\n",
    "            if sum(int(c) for c in str(n + res)) <= target:\r\n",
    "                return res\r\n",
    "            d *= 10\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeIntegerBeautiful(self, n: int, target: int) -> int:\n",
    "        i = 0\n",
    "        while True:\n",
    "            temp = n+i\n",
    "            temp = str(temp)\n",
    "            sum1 = 0\n",
    "            the_len = 1\n",
    "            for j in range(len(temp)):\n",
    "                sum1 += int(temp[j])\n",
    "                if sum1>target:\n",
    "                    the_len = len(temp[j:])\n",
    "                    flag = int(temp[j:])\n",
    "                    break\n",
    "            if sum1<=target:\n",
    "                return i\n",
    "            i +=  10**(the_len)-flag\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeIntegerBeautiful(self, num: int, target: int) -> int:\n",
    "        def check(num):\n",
    "            res = 0\n",
    "            while num:\n",
    "                res += num % 10 \n",
    "                num //= 10 \n",
    "            return res <= target\n",
    "        res = 0\n",
    "        base = 1\n",
    "        while not check(num):\n",
    "            digit = num % 10 \n",
    "            if digit == 0:\n",
    "                num //= 10 \n",
    "                base *= 10 \n",
    "                continue \n",
    "            res += (10 - digit) * base \n",
    "            base *= 10 \n",
    "            num  = (num + 10) // 10\n",
    "        return res \n",
    "\n",
    "\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeIntegerBeautiful(self, n: int, target: int) -> int:\n",
    "        nums = []\n",
    "        tsum = 0\n",
    "        while(n > 0):\n",
    "            nums.append(n % 10)\n",
    "            tsum += n % 10\n",
    "            n = n // 10\n",
    "        if(tsum <= target):\n",
    "            return 0 \n",
    "        nums.append(0)\n",
    "        result = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if(nums[i] == 0):\n",
    "                continue\n",
    "            result += (10-nums[i])*10**i\n",
    "            tsum -= nums[i]\n",
    "            nums[i] = 0\n",
    "            carry = 1\n",
    "            for j in range(i+1,n):\n",
    "                if(nums[j] + carry < 10):\n",
    "                    tsum += carry\n",
    "                    nums[j] += carry\n",
    "                    break\n",
    "                else:\n",
    "                    tsum -= nums[j]\n",
    "                    nums[j] = 0\n",
    "                    carry = 1\n",
    "            if(tsum <= target):\n",
    "                return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeIntegerBeautiful(self, n: int, target: int) -> int:\n",
    "        nums = []\n",
    "        tsum = 0\n",
    "        while(n > 0):\n",
    "            nums.append(n % 10)\n",
    "            tsum += n % 10\n",
    "            n = n // 10\n",
    "        if(tsum <= target):\n",
    "            return 0 \n",
    "        nums.append(0)\n",
    "        result = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if(nums[i] == 0):\n",
    "                continue\n",
    "            result += (10-nums[i])*10**i\n",
    "            tsum -= nums[i]\n",
    "            nums[i] = 0\n",
    "            carry = 1\n",
    "            for j in range(i+1,n):\n",
    "                if(nums[j] + carry < 10):\n",
    "                    tsum += carry\n",
    "                    nums[j] += carry\n",
    "                    break\n",
    "                else:\n",
    "                    tsum -= nums[j]\n",
    "                    nums[j] = 0\n",
    "                    carry = 1\n",
    "            if(tsum <= target):\n",
    "                return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeIntegerBeautiful(self, n: int, target: int) -> int:\n",
    "        def check(num):\n",
    "            res = 0\n",
    "            while num:\n",
    "                res += num % 10 \n",
    "                num //= 10 \n",
    "            return res <= target\n",
    "        res = 0\n",
    "        base = 1 \n",
    "        while not check(n):\n",
    "            digit = n % 10 \n",
    "            if digit == 0:\n",
    "                base *= 10 \n",
    "                n //= 10 \n",
    "                continue \n",
    "            res += (10 - digit) * base\n",
    "            base *= 10 \n",
    "            n = (n + 10) // 10 \n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeIntegerBeautiful(self, n: int, target: int) -> int:\n",
    "        t = list(str(n))[::-1]\n",
    "        s = list(map(int, t))\n",
    "        # print(f\"s => {s}\")\n",
    "        l = len(s)\n",
    "        r = [0] * l\n",
    "        s += [0]\n",
    "        p = 0\n",
    "        while sum(s) > target:\n",
    "            # print(f\"s {s}\")\n",
    "            v = s[p]\n",
    "            if v > 0:\n",
    "                a = 10 - v\n",
    "                r[p] = a\n",
    "                s[p] = 0\n",
    "                n = p + 1\n",
    "                while s[n] == 9:\n",
    "                    s[n] = 0\n",
    "                    n += 1\n",
    "                s[n] += 1\n",
    "            p += 1\n",
    "        # print(f\"s {s} r{r}\")\n",
    "        ret = 0\n",
    "        for v in r[::-1]:\n",
    "            ret = ret * 10 + v\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeIntegerBeautiful(self, n: int, target: int) -> int:\n",
    "        a = []\n",
    "        while n > 0:\n",
    "            a.append(n % 10)\n",
    "            n //= 10\n",
    "        a.append(0)\n",
    "        res, s, p, n = 0, sum(a), 1, len(a)\n",
    "        for i in range(n):\n",
    "            if s <= target:\n",
    "                break\n",
    "            if a[i] > 0:\n",
    "                res += (10 - a[i]) * p\n",
    "                s += 1 - a[i]\n",
    "                a[i] = 0\n",
    "                a[i+1] += 1\n",
    "                j = i + 1\n",
    "                while a[j] == 10:\n",
    "                    a[j] = 0\n",
    "                    j += 1\n",
    "                    a[j] += 1\n",
    "                    s -= 9\n",
    "            p *= 10\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 暴力枚举-超时\n",
    "class Solution:\n",
    "    def makeIntegerBeautiful(self, n: int, target: int) -> int:\n",
    "        def check(x,target):\n",
    "            total=0\n",
    "            while x!=0:\n",
    "                total+=x%10\n",
    "                x=x//10\n",
    "            return total<=target\n",
    "\n",
    "        for i in range(10**12):\n",
    "            if check(i+n,target):\n",
    "                return i\n",
    "\n",
    "class Solution:\n",
    "    def makeIntegerBeautiful(self, n: int, target: int) -> int:\n",
    "        def check(num,target):\n",
    "            total=0\n",
    "            while num!=0:\n",
    "                total+=num%10\n",
    "                num=num//10\n",
    "            return total<=target\n",
    "        a=n\n",
    "        while not check(a,target):\n",
    "            x=a\n",
    "            i,j=0,0\n",
    "            while x!=0:\n",
    "                j=x%10\n",
    "                x=x//10\n",
    "                i+=1\n",
    "                if j!=0:\n",
    "                    break\n",
    "            a+=(10-j)*(10**(i-1))\n",
    "        return a-n\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeIntegerBeautiful(self, n: int, target: int) -> int:\n",
    "        tail = 1\n",
    "        while True:\n",
    "            s = 0\n",
    "            m = x = n + (tail - n % tail) % tail\n",
    "            while x:\n",
    "                s += x % 10\n",
    "                x //= 10\n",
    "\n",
    "            if s <= target:\n",
    "                return m - n\n",
    "            \n",
    "            tail *= 10\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeIntegerBeautiful(self, n: int, t: int) -> int:\n",
    "        n=[0]+[int(i) for i in str(n)]\n",
    "        def g(n,i):\n",
    "            n[i]=10\n",
    "            while n[i]>=10:\n",
    "                n[i]-=10\n",
    "                i-=1\n",
    "                n[i]+=1\n",
    "        s=sum(n)\n",
    "        if s<=t:\n",
    "            return 0\n",
    "        m=len(n)\n",
    "        ans=[0 for i in range(m)]\n",
    "        for i in reversed(range(m)):\n",
    "            if n[i]>0:\n",
    "                ans[i]=10-n[i]\n",
    "                g(n,i)\n",
    "                s=sum(n)\n",
    "                if s<=t:\n",
    "                    break\n",
    "        return int(''.join(str(i) for i in ans))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeIntegerBeautiful(self, n: int, target: int) -> int:\n",
    "        \n",
    "        res ,k= 0,1\n",
    "        while n%10 == 0:\n",
    "            n//=10\n",
    "            k*=10\n",
    "        sm = sum([int(i) for i in str(n)])\n",
    "        while sm > target:\n",
    "            res += (10-n%10)*k\n",
    "            sm -= n%10-1\n",
    "            n = n//10+1\n",
    "            print(sm)\n",
    "            while n%10 == 0:\n",
    "                sm -= 9\n",
    "                n //= 10\n",
    "                k*=10\n",
    "                print(sm)\n",
    "            k*=10\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeIntegerBeautiful(self, n: int, target: int) -> int:\n",
    "        sn = list(map(int, str(n)))\n",
    "        accu = list(accumulate(sn))\n",
    "        if accu[-1] <= target: return 0\n",
    "        i = bisect_left(accu, target)\n",
    "        i -= 1\n",
    "        while i >= 0 and sn[i] == 9:\n",
    "            i -= 1\n",
    "        for j in range(i+1, len(sn)):\n",
    "            sn[j] = 0\n",
    "        if i >= 0: \n",
    "            sn[i] += 1\n",
    "            it = sn\n",
    "        else:\n",
    "            it = chain([1], sn)\n",
    "        return reduce(lambda a, b: a*10+b, it, 0) - n\n",
    "\n",
    "\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeIntegerBeautiful(self, n: int, target: int) -> int:\n",
    "        tail = 1\n",
    "        while True:\n",
    "            m = x = n + (tail - n % tail) % tail\n",
    "            s = 0\n",
    "            while x:\n",
    "                s += x % 10\n",
    "                x //= 10\n",
    "            if s <= target: return m - n\n",
    "            tail *= 10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeIntegerBeautiful(self, n: int, target: int) -> int:\n",
    "        def carry(num: int) -> int:\n",
    "            \"\"\"最低的非0位进位(carry)\n",
    "\n",
    "            16 -> 20\n",
    "            19 -> 20\n",
    "            20 -> 100\n",
    "            101 -> 110\n",
    "            110 -> 200\n",
    "            \"\"\"\n",
    "            base = 10\n",
    "            while True:\n",
    "                div, mod = divmod(num, base)\n",
    "                if mod == 0:\n",
    "                    base *= 10\n",
    "                else:\n",
    "                    return (div + 1) * base\n",
    "\n",
    "        cur = n\n",
    "        while True:\n",
    "            if sum(map(int, str(cur))) <= target:\n",
    "                return cur - n\n",
    "            cur = carry(cur)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeIntegerBeautiful(self, n: int, target: int) -> int:\n",
    "        nums = []\n",
    "        tsum = 0\n",
    "        while(n > 0):\n",
    "            nums.append(n % 10)\n",
    "            tsum += n % 10\n",
    "            n = n // 10\n",
    "        if(tsum <= target):\n",
    "            return 0 \n",
    "        nums.append(0)\n",
    "        result = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if(nums[i] == 0):\n",
    "                continue\n",
    "            result += (10-nums[i])*10**i\n",
    "            tsum -= nums[i]\n",
    "            nums[i] = 0\n",
    "            carry = 1\n",
    "            for j in range(i+1,n):\n",
    "                if(nums[j] + carry < 10):\n",
    "                    tsum += carry\n",
    "                    nums[j] += carry\n",
    "                    break\n",
    "                else:\n",
    "                    tsum -= nums[j]\n",
    "                    nums[j] = 0\n",
    "                    carry = 1\n",
    "            if(tsum <= target):\n",
    "                return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeIntegerBeautiful(self, n: int, target: int) -> int:\n",
    "        res = 0\n",
    "        ls = [int(c) for c in str(n)]\n",
    "        Sum = sum(ls)\n",
    "        if Sum<=target:\n",
    "            return 0\n",
    "        flag = 1\n",
    "        ls[-1] -= 1\n",
    "        for i in ls[::-1]:\n",
    "            print(res, flag, Sum)\n",
    "            res += (9-i)*flag\n",
    "            flag *= 10\n",
    "            Sum -= i\n",
    "            if Sum<=target:\n",
    "                return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeIntegerBeautiful(self, n: int, target: int) -> int:\n",
    "        # 凑数\n",
    "        if sum(int(i) for i in str(n)) <= target:\n",
    "            return 0\n",
    "        sn = str(n)\n",
    "        l = len(sn)\n",
    "        for i, v in enumerate(sn):\n",
    "            target -= int(v)\n",
    "            if target <= 0:\n",
    "                return 10**(l-i) - int(sn[i:])\n",
    "        return 0\n",
    "\n",
    "        # TLE - 暴力 除法\n",
    "        x = 0\n",
    "        while 1:\n",
    "            num = n + x\n",
    "            s = 0\n",
    "            while num:\n",
    "                s += num % 10\n",
    "                num = num // 10\n",
    "            if s <= target:\n",
    "                 return x\n",
    "            x += 1\n",
    "\n",
    "        # TLE - 暴力 转换\n",
    "        x = 0\n",
    "        while 1:\n",
    "            if sum(int(i) for i in str(n + x)) <= target:\n",
    "                return x\n",
    "            x += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeIntegerBeautiful(self, n: int, target: int) -> int:\n",
    "        nums = [int(i) for i in str(n)]\n",
    "        while target < sum(nums):\n",
    "            i = len(nums)-1\n",
    "            while i >=0:\n",
    "                if nums[i]>0:\n",
    "                    nums[i] = 0\n",
    "                    if i-1>=0:\n",
    "                        nums[i-1]+=1\n",
    "                    else:\n",
    "                        nums.insert(0, 1)\n",
    "                    break\n",
    "                i-=1\n",
    "            while 10 in nums:\n",
    "                index = nums.index(10)\n",
    "                if index == 0:\n",
    "                    nums[0] = 0\n",
    "                    nums.insert(0, 1)\n",
    "                else:\n",
    "                    nums[index] = 0\n",
    "                    nums[index-1] +=1\n",
    "        s2 = int(\"\".join([str(i) for i in nums]))\n",
    "        return s2 - n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeIntegerBeautiful(self, n: int, target: int) -> int:\n",
    "        a = n\n",
    "        k = 0\n",
    "        while a:\n",
    "            k += a % 10\n",
    "            a //= 10\n",
    "        if k <= target:\n",
    "            return 0\n",
    "        def cal_sum(num):\n",
    "            cnt = 0\n",
    "            while num:\n",
    "                cnt += num % 10\n",
    "                num //= 10\n",
    "            return cnt\n",
    "        a = n\n",
    "        delta = 0\n",
    "        total_delta = 0\n",
    "        exp = 0\n",
    "        while a:\n",
    "            delta = 10 - a % 10\n",
    "            total_delta += 10 ** exp * delta\n",
    "            a += delta\n",
    "            # print(a, delta)\n",
    "            if cal_sum(a) <= target:\n",
    "                # print(a, cal_sum(a), delta,target)\n",
    "                return total_delta\n",
    "            a //= 10\n",
    "            exp += 1\n",
    "        return delta\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeIntegerBeautiful(self, n: int, target: int) -> int:\n",
    "        t, s = n, 0\n",
    "        while t:\n",
    "            s += t % 10\n",
    "            t //= 10\n",
    "        if s <= target: return 0\n",
    "        t, ca = n, 0\n",
    "        d = 0\n",
    "        while True:\n",
    "            if s + ca <= target:\n",
    "                break\n",
    "            s -= t % 10\n",
    "            t //= 10\n",
    "            ca = 1\n",
    "            d += 1\n",
    "            print(f'{s},{t}')\n",
    "        m = 10 ** d\n",
    "        return m + (n // m) * m - n\n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeIntegerBeautiful(self, n: int, target: int) -> int:\n",
    "        bits = []\n",
    "        tmp = n\n",
    "        while tmp:\n",
    "            bits.append(tmp % 10)\n",
    "            tmp //= 10\n",
    "        \n",
    "        if sum(bits) <= target:\n",
    "            return 0\n",
    "        now = 0\n",
    "        ten = 1\n",
    "        for b in bits:\n",
    "            now += ten * b\n",
    "            ten *= 10\n",
    "            if now:\n",
    "                add = ten - now\n",
    "                tmp = n + add\n",
    "                cnt = 0\n",
    "                while tmp:\n",
    "                    cnt += tmp % 10\n",
    "                    tmp //= 10\n",
    "                if cnt <= target:\n",
    "                    return add\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeIntegerBeautiful(self, n: int, target: int) -> int:\n",
    "        def poly(arr):\n",
    "            temp = 0\n",
    "            for k in arr:\n",
    "                temp = 10 * temp + k\n",
    "            return temp\n",
    "\n",
    "        temp = []\n",
    "        nn = n\n",
    "        while nn:\n",
    "            temp.append(nn % 10)\n",
    "            nn //= 10\n",
    "        temp.append(0)\n",
    "        temp = temp[::-1]\n",
    "        m = len(temp)\n",
    "        p = 0\n",
    "        pre = 0\n",
    "        while p < m and pre < target:\n",
    "            pre += temp[p]\n",
    "            p += 1\n",
    "        if pre < target:\n",
    "            return 0\n",
    "        elif pre == target:\n",
    "            pp = p\n",
    "            while pp < m:\n",
    "                if temp[pp] != 0:\n",
    "                    return poly(temp[:p-2] + [temp[p-2] + 1] + [0] * (m-p+1)) - n\n",
    "                pp += 1\n",
    "            else:\n",
    "                return 0\n",
    "        else:\n",
    "            return poly(temp[:p-2] + [temp[p-2] + 1] + [0] * (m-p+1)) - n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeIntegerBeautiful(self, n: int, target: int) -> int:\n",
    "        def sum_of_digits(num: int) -> int:\n",
    "            return sum(int(digit) for digit in str(num))\n",
    "\n",
    "        current_sum = sum_of_digits(n)\n",
    "        if current_sum <= target:\n",
    "            return 0\n",
    "\n",
    "        x = 0\n",
    "        factor = 1\n",
    "        while current_sum > target:\n",
    "            last_digit = n % 10\n",
    "            x += (10 - last_digit) * factor\n",
    "            n = (n // 10) + 1\n",
    "            factor *= 10\n",
    "            current_sum = sum_of_digits(n)\n",
    "\n",
    "        return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeIntegerBeautiful(self, n: int, target: int) -> int:\n",
    "        def bit_sum(n):\n",
    "            return sum([int(i) for i in str(n)])\n",
    "\n",
    "        if bit_sum(n) <= target:\n",
    "            return 0\n",
    "        \n",
    "        bits = len(str(n))\n",
    "        for i in range(bits-1, -1, -1):\n",
    "            diff = 10 ** (bits-i) - n % (10 ** (bits-i))\n",
    "            if bit_sum(n + diff) <= target:\n",
    "                return diff\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeIntegerBeautiful(self, n: int, target: int) -> int:\n",
    "        def total(x):\n",
    "            ans = 0\n",
    "            while x:\n",
    "                ans += x % 10\n",
    "                x //= 10\n",
    "            return ans\n",
    "        \n",
    "        mask = 10\n",
    "        m = n\n",
    "        while total(m) > target:\n",
    "            m += mask - m % mask\n",
    "            mask *= 10\n",
    "        return m - n\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeIntegerBeautiful(self, n: int, target: int) -> int:\n",
    "        tail = 1\n",
    "        while True:\n",
    "            m = x = n + (tail - n % tail) % tail  # 进位后的数字\n",
    "            s = 0\n",
    "            while x:\n",
    "                s += x % 10\n",
    "                x //= 10\n",
    "            if s <= target: return m - n\n",
    "            tail *= 10\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeIntegerBeautiful(self, n: int, target: int) -> int:\n",
    "        tail = 1\n",
    "        while True:\n",
    "            m = x = n + (tail - n % tail) % tail  # 进位后的数字\n",
    "            s = 0\n",
    "            while x: # 这里是求和的部分\n",
    "                s += x % 10\n",
    "                x //= 10\n",
    "            if s <= target: return m - n\n",
    "            tail *= 10\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeIntegerBeautiful(self, n: int, target: int) -> int:\n",
    "        def bit_sum(n):\n",
    "            return sum([int(i) for i in str(n)])\n",
    "\n",
    "        if bit_sum(n) <= target:\n",
    "            return 0\n",
    "        \n",
    "        bits = len(str(n))\n",
    "        for i in range(bits-1, -1, -1):\n",
    "            diff = 10 ** (bits-i) - int(str(n)[i:])\n",
    "            if bit_sum(n + diff) <= target:\n",
    "                return diff\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
